package com.leetcode.demo;

/**
 * @author 王溪源
 * @ClassName: Question35
 * @Description: 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 *
 * 请必须使用时间复杂度为 O(log n) 的算法。
 * 用二分查找
 * @Date 2021/8/26 23:36
 * @see Question69#mySqrt2(int) 
 **/
public class Question35 {
    public static int searchInsert(int[] nums, int target) {
        int start = 0;
        int end = nums.length;
        int mid = (start + end ) / 2;
        // 二分查找
        while (mid > start && mid < end){
            if (target > nums[mid]){
                start = mid;
                mid = (mid + end) / 2;
            }
            if(target < nums[mid]){
                end = mid;
                mid = (start + mid) / 2;
            }
            if(target == nums[mid]){
                return mid;
            }
        }
        return target > nums[mid] ? mid + 1 : mid;
    }

    public static int searchInsert2(int[] nums, int target) {
        int len = nums.length;
        int left = 0;
        int right = len;
        // 在区间 nums[left..right] 里查找第 1 个大于等于 target 的元素的下标
        while (left < right) {
            // 计算中间坐标的这种方式我没考虑到 我是用的是 (right + left) >> 1
            int mid = ((right - left) >> 1) + left;
            if (nums[mid] < target){
                // 下一轮搜索的区间是 [mid + 1..right]
                left = mid + 1;
            } else {
                // 下一轮搜索的区间是 [left..mid]
                right = mid;
            }
        }
        return left;
    }

    public static void main(String[] args) {
        // 0 1 2 3
        int[] nums = {1,3,5,6};
        int[] nums2 = {1,3};
//        System.out.println (searchInsert (nums,5));
//        System.out.println (searchInsert (nums,2));
//
//        System.out.println (searchInsert (nums,1));
//
        System.out.println (searchInsert2 (nums,7));

        System.out.println (searchInsert2 (nums2,0));// 4
    }
}
